00100	.PAGE FRAME 54 HIGH 80 WIDE
00200	.COUNT PAGE FROM 0
00300	.PORTION TITLEPAGE
00400	.BEGIN
00500	.CENTER
00600	.SKIP TO LINE 20
00700	THE PROGRAMMING LANGUAGE "LISP70"
00800	
00900	LAWRENCE G. TESLER, HORACE J. ENEA, AND DAVID C. SMITH
01000	
01100	STANFORD UNIVERSITY
01200	ARTIFICIAL INTELLIGENCE PROJECT
01300	
01400	FEBRUARY, 1972
01500	.END
01600	.PORTION REPORT
01700	.INDENT 5,0
01800	.MACRO BC ⊂ BEGIN GROUP CENTER SKIP 1 ; ⊃
01900	.MACRO ec ⊂ SKIP 1 ; END CONTINUE ⊃
02000	.MACRO e ⊂ SKIP 1 ; END ⊃
02100	.TURN ON "↓_[]#α∂"
02200	.MACRO s(N) ⊂ SNAME←DATE ; NEXT PAGE ONCE CENTER ; "N" ;
02300	.	SKIP 2 ; SNAME ← "N" ⊃ ;
02400	.EVERY HEADING(LISP70,,{SNAME})
02500	.EVERY FOOTING(,{PAGE},)
     

00100	.S INTRODUCTION
00200	The language LISP [ref McCarthy] deals with recursive functions of symbolic
00300	expressions.  There has recently emerged a trend towards creating 
00400	"New LISPs" offering additional capabilities.  Of primary interest are
00500	expanded control structures, including backtracking and multiple
00600	processing.  Also of importance are varied methods of data access,
00700	such as associative data bases.  The question of an appropriate successor
00800	to LISP is discussed elsewhere [ref Bobrow].
00900	
01000	Some of the "New LISPs" that are currently under development are PLANNER
01100	at MIT [ref Hewitt], QA-4 at SRI [ref Rulifson], POP-2 at ?? [ref ??],
01200	and LISP70, the subject of the present paper.  Having
01300	evolved separately, they differ somewhat in detail.  However, their
01400	similarities are more striking than their differences.  All provide
01500	convenient vehicles for theorem proving, robot planning, natural
01600	language processing, and other complex problem solving tasks.
01700	
01800	LISP70 is distinguished from the other "New LISPs" primarily by its
01900	extendability.  The design goals of the language, in approximate order
02000	of importance, are:
02100	.bc
02200	(1) Extendability		#
02300	(2) Inter-machine transferability
02400	(3) Facilitated debugging	#
02500	(4) Convenient input and output	#
02600	(5) Efficiency of operation	#
02700	.ec
02800	Each of these goals will be discussed separately.
     

00100	.S EXTENDABILITY
00200	Every extendable language consists of a "core" and a method of extending
00300	that core.  The core of LISP70 is actually much larger than necessary;
00400	that is, most parts of the core are defined in terms of more primitive
00500	parts.  Some of the facilities offered are:
00600	.bc
00700	(1) LISP 1.5, a common standard [ref]					#
00800	(2) MLISP, an Algol-like M-expression notation [ref Enea, ref Smith]	#
00900	(3) Automatic Backtracking [ref Floyd]					#
01000	(4) Pattern-Directed Computation					#
01100	(5) Syntax-Directed Input-Output					#
01200	(6) Extensive monitoring capabilities					#
01300	(7) A variety of data types						#
01400	(8) "Extendable Functions"						#
01500	.e
01600	An Extendable Function is a function which is defined by an open-ended
01700	set of "rewrite rules" [ref somebody].
01800	The "EXTEND Statement" adds new rules to an Extendable Function.
01900	The LISP70 compilers are defined primarily in terms of Extendable Functions.
02000	Thus, anyone can extend them by use of appropriate EXTEND Statements.  The
02100	scope of an extension can be a whole program or any part of a program.
     

00100	.S EXTENDING MLISP
00200	MLISP is defined entirely by Extendable Functions such as "EXPRESSION",
00300	which translates an M-expression to an S-expression.  For example, the
00400	conditional expression of MLISP is defined in terms of the conditional
00500	expression of LISP by the following rewrite rule in EXPRESSION:
00600	.bc
00700	⊂IF <expression>:e1 THEN <expression>:e2 ELSE <expression>:e3⊃	#
00800		→→ (COND (:e1 :e2) (T :e3))				#
00900	.ec
01000	Every rewrite rule has a left side and a right side separated by right-pointing
01100	arrows.  A rewrite rule can translate any input that matches its left
01200	side to an output constructed by its right side.  Strictly local variables
01300	(preceded by the character ":") serve to carry information from the left
01400	side to the right side.
01500	
01600	The above rule for translating conditionals is read from left to right
01700	as follows:
01800	.begin narrow 10,10
01900	An input stream ("⊂...⊃") which begins with the symbol `IF', followed
02000	by an <expression> (whose translation is bound to e1), followed by
02100	`THEN', followed by another <expression> (whose translation is
02200	bound to e2), followed by `ELSE', followed by another <expression>
02300	(whose translation is bound to e3), can definitely ("→→") be rewritten
02400	as a list of the following three elements: first, the symbol `COND';
02500	second, a list containing the binding of e1 and the binding of e2;
02600	finally, a list containing `T' and the binding of e3.
02700	.end skip
02800	Each of the three occurrences of <expression> within this definition calls
02900	EXPRESSION recursively to translate portions of the conditional.  Should
03000	any of these calls fail, the entire rewrite rule fails and a different
03100	rule of EXPRESSION is tried.  Thus, more than one rule of the syntax may
03200	begin with the symbol `IF'.  In fact, it is possible to define arbitrarily
03300	context-sensitive grammars with LISP70 rewrite rules, but this subject will
03400	not be explored here.
03500	
03600	As an illustration of the operation of the above rewrite rule, the
03700	processing of the following input stream will be traced:
03800	.bc
03900	if a=b then 7 else cons(7,a)
04000	.ec
04100	After `IF' is matched, `a=b' is translated by a recursive call on EXPRESSION to
04200	`(EQUAL A B)', which is bound to e1.  The other local variables are bound
04300	in a similar manner, yielding:
04400	.bc
04500	e1 = (EQUAL A B)#
04600	e2 = 7		#
04700	e3 = (CONS 7 A)	#
04800	.ec
04900	These bindings are substituted into the right hand side, outputting the
05000	translation:
05100	.bc
05200	(COND  ((EQUAL A B) 7)  (T (CONS 7 A)) )
05300	.e
05400	Example:
05500	.bc
05600	extendable function simplify =				#
05700		(PLUS 0 ::X) →→ (PLUS ::X)*,			#
05800		(PLUS :A ::B) →→ (PLUS :A (PLUS ::B)*@@CDR),	#
05900		(PLUS) →→ 0 ;					#
06000	.e
06100	Some notation must be explained:
06200	.bc
06300		:X	Matches any one item and binds it to X.		#
06400		:X	On right side: the binding of X.		#
06500		::X	Matches zero or more items, forms them into	#
06600				a list, binds that list to X.		#
06700		::X	On right side: the elements of X, i.e., the list#
06800				X with its outer parentheses stripped.	#
06900		@F	Postfix Function Call:  Call function F with the#
07000				preceding value as its argument, e.g.,	#
07100				((A) B C)@CAR yields (A).		#
07200		@@F	Call F and strip the result, e.g., 		#
07300				((A) B C)@@CAR yields A.		#
07400		*	Call the current function recursively, i.e.,	#
07500				same as @SIMPLIFY.			#
07600		**	In this case, same as @@SIMPLIFY.		#
07700		(...)	Match or construct a list.			#
07800		⊂...⊃	Match or construct a stream.			#
07900		`...'	Same as ⊂...⊃, but no special characters are	#
08000			recognized except <>*@:				#
08100	.e
08200	Let us trace the call (SIMPLIFY (QUOTE (PLUS HAT 0 J K))).
08300	.bc
08400	Argument	Rule Applied	Result
08500	--------	---- -------	------
08600	
08700	(PLUS HAT 0 J K))	2	(PLUS HAT (PLUS 0 J K)*@@CDR)	#
08800	(PLUS 0 J K)		1	(PLUS J K)*			#
08900	(PLUS J K)		2	(PLUS J (PLUS K)*@@CDR)		#
09000	(PLUS K)		2	(PLUS K (PLUS)*@@CDR)		#
09100	(PLUS)			3	(PLUS)				#
09200	
09300	Expression		After *			After CDR	After STRIP
09400	----------		-------			--------- 	-----------
09500		
09600	(PLUS)*@@CDR		(PLUS)@@CDR		()@STRIP	⊂ ⊃	  #
09700	(PLUS K)*@@CDR		(PLUS K)@@CDR		(K)@@STRIP	K	  #
09800	(PLUS 0 J K)*@@CDR	(PLUS J K)@@CDR		(J K)@STRIP	J K	  #
09900	.ec
10000	When several rules occur in an extendable function, they are ordered Most
10100	Specific First.  If the left side of the first rule matches the input,
10200	then the value of the function is computed by the right side of that rule.
10300	Otherwise, subsequent rules are tried in the same way.  If no rule matches,
10400	a failure occurs, causing backtracking.
10500	
10600	Proper ordering of rules is important both for speed and correctness.
10700	In the compiler, the Most Specific First heuristic is trivial to
10800	implement.  For example, if the left sides of two rules are identical
10900	up to a point at which one has a literal symbol and the other has a
11000	local variable binding, then the former rule is ordered before the
11100	latter.  This is because the literal symbol can only match one possible
11200	input entity while the local variable binding can match anything.